<<<<<<< HEAD
/*
** 单链表的冒泡排序
** auther:zhuchaoyang
** date:2014/8/25
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>
#define LINKEDLIST_SIZE 100 //宏定义链表的长度
#define MAX_VALUE 1000 //宏定义链表中随机数的最大值
#define nodelen sizeof(struct node) //宏定义节点长度
#define NULL ((void *)0)  //此行要不要没关系

/*
** 定义结构体
*/
typedef struct node //定义名为node的结构体
{
    long num;
    struct node * next;
} Lnode;   //声明为Lnode新类型名
/*
**建立随机链表
*/
Lnode * creat(void) //定义建立链表函数，此函数带回一个指向链表头的指针
{
    int i=0;
    Lnode * head; //定义头指针
    Lnode * pfast,* pslow; //快指针，慢指针
    head = (Lnode *)malloc(nodelen); //malloc函数值是一个分配域起始地址
    pfast = head->next;
    pslow = head;
    //head->num = NULL;
    srand((int)time(0)); //随机种子
    for(i=0;i<LINKEDLIST_SIZE;i++)
    {
        pfast = (Lnode *)malloc(nodelen);
        pfast -> num = (int)(rand() % MAX_VALUE); //附一个随机数
        /*if(i==0)
        {
            head->next = pfast; //指向第一个节点指针为头指针
        }
        else
        {
            pslow -> next = pfast; //否则指针域指向下个节点     
        }*/
        
        pslow->next = pfast;
        pslow = pfast;
        
    }
    pslow -> next = NULL; 
    return(head); //返回头指针
}

/*
** 交换函数
*/
void exchange(Lnode** p1,Lnode** p2)
{
   // Lnode* pk,* pk1;
   // pk = p11->next;
   // pk1 = p2->next;
   // p11->next = p22->next;
   // p2->next = p1->next;
   // p22->next = pk;
   // p1->next = pk1;
    Lnode* temp = *p1;
    *p1 = *p2;
    *p2 = temp;

    temp = (*p1)->next;
    (*p1)->next = (*p2)->next;
    (*p2)->next = temp;
}

/*
** 对已建立的链表进行冒泡排序
*/
Lnode* bubblesort(Lnode* head) //建立参数为指向链表头指针的函数，并且返回同样的一个指向链表头指针head
{
    Lnode** pslow,** pfast;
    pslow = &head->next;
    pfast = &head->next;
   // Lnode* pfast,* pslow;
   // Lnode* ppfast,* ppslow;
   // pslow=ppslow=ppfast=head;
   // pfast=pslow->next; //快指针指向慢指针指向的下一个节点
    int i,j;  //i,j为循环参数
    for(i=0;i<LINKEDLIST_SIZE-1;i++) //从第一个节点循环
    {
        for(j=i+1;j<LINKEDLIST_SIZE;j++) //快指针从慢指针指向的下一个节点循环到最后
        {
            if((*pslow)->num > (*pfast)->num)  //比较大小
            {
                exchange(pslow,pfast);  
               // pfast = pfast->next;
               // ppfast = ppfast->next;
                
                pfast = &(*pfast)->next;
                      
            }
            else
            {
                pfast = &(*pfast)->next; //循环到最后时，*pfast->next指向NULL
               // ppfast = ppfast->next;
            }
        }
       // ppslow = pslow;
       // pslow = pslow->next; //慢指针向下一个节点移动
       // pfast = pslow->next; //对快指针重新赋值，为慢指针所指向的下一个节点
       // ppfast = pslow;
       pslow = &(*pslow)->next;
       pfast = &(*pslow)->next;
    }
    return(head);
}

/*
** 输出链表
*/
void print(Lnode* head) //建立以头指针为参数的输出函数
{
    Lnode* p;
    p=head;
    while(p != NULL)
    {
        printf("%ld\n",p->num);
        p=p->next;
    }
}

/*
** 主函数
*/
void main()
{
    Lnode* head;
    head = creat();
    print(bubblesort(head));
}
=======
/*
** 单链表的冒泡排序
** auther:zhuchaoyang
** date:2014/8/25
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>
#define LINKEDLIST_SIZE 100 //宏定义链表的长度
#define MAX_VALUE 1000 //宏定义链表中随机数的最大值
#define nodelen sizeof(struct node) //宏定义节点长度
#define NULL ((void *)0)  //此行要不要没关系

/*
** 定义结构体
*/
typedef struct node //定义名为node的结构体
{
    long num;
    struct node * next;
} Lnode;   //声明为Lnode新类型名
/*
**建立随机链表
*/
Lnode * creat(void) //定义建立链表函数，此函数带回一个指向链表头的指针
{
    int i=0;
    Lnode * head; //定义头指针
    Lnode * pfast,* pslow; //快指针，慢指针
    pfast = pslow = (Lnode *)malloc(nodelen); //malloc函数值是一个分配域起始地址
    head=NULL;
    srand((int)time(0)); //随机种子
    for(i=0;i<LINKEDLIST_SIZE;i++)
    {
        pfast -> num = rand() % MAX_VALUE; //为第一个节点附一个随机数
        if(i==0)
        {
            head = pfast; //指向第一个节点指针为头指针
        }
        else
        {
            pslow -> next = pfast; //否则指针域指向下个节点     
        }
        pslow = pfast;
        pfast = (Lnode *)malloc(nodelen);
    }
    pslow -> next = NULL; 
    return(head); //返回头指针
}

/*
** 交换函数
*/
void exchange(Lnode** p1, Lnode** p2)
{
    Lnode* temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

/*
** 对已建立的链表进行冒泡排序
*/
Lnode* bubblesort(Lnode* head) //建立参数为指向链表头指针的函数，并且返回同样的一个指向链表头指针head
{
    Lnode** pfast = &head->next;
    Lnode** pslow = &head->next; 
    pfast = &(*pfast)->next;       //此行代码按照操作符的优先级相当于 pfast = &((*pfast)->next); 
    int i,j;  //i,j为循环参数
    
    for(i=0; i<LINKEDLIST_SIZE-1; i++) //从第一个节点循环
    {
        for(j=i+1; j<LINKEDLIST_SIZE; j++) //快指针从慢指针指向的下一个节点循环到最后
        {
            if((*pslow)->num > (*pfast)->num)  //比较大小
            {
                exchange(pslow, pfast); 
                pfast = &(*pfast)->next; 
            }
        } 
        pslow = &(*pslow)->next; //慢指针向下一个节点移动
        pfast = &head->next; //对快指针重新赋值，为慢指针所指向的下一个节点 
    }
    return(head);
}

/*
** 输出链表
*/
void print(Lnode* head) //建立以头指针为参数的输出函数
{
    Lnode* p;
    p=head;
    while(p != NULL)
    {
        printf("%ld\n",p->num);
        p=p->next;
    }
}

/*
** 主函数
*/
void main()
{
    Lnode* head;
    head = creat();
    print(bubblesort(head));
}
>>>>>>> e798146c5deaec438f4229a1bb4ab2d7691b7d3d
